package com.itheima.demo6;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class MyLinkedList<E> {
    //记录链表的总长度，在每一次加结点的时候，都需要++
    private int size;
    /**
     * 定义了一个私有的内部类，作为链表的结点。
     *  linkedList的addLast源码里面也是这样类似写的，定义的是静态内部类
     *  Node泛型类，用于代表链表的结点。每个结点包含（数据data，和下一个结点的地址值next）
     */
    public static class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    public Node<E> add(){
        Node<E> head = null;    //头结点
        Scanner sc = new Scanner(System.in);
        while (true) {
            System.out.println("请输入要添加的链表结点值：");
            String data = sc.next();
            if(data.equals("exit")) break;
            //第一次创建结点，无头结点，初始化头结点
            if(head == null) {
                head = new Node(data, null);
                size++;
            }else {
                //说明已经有头结点，直接往整个链表的尾部，往后面插入结点。（尾插法）
                //保存头结点，把头结点复制给temp临时节点，用来遍历链表，最终指向链表的最后一个结点尾节点
                Node<E> temp = head;
                // 让temp走到尾部结点：如果temp.next=null，也就是说temp一直往下指，当指向的下一个元素为null，就说明到了尾部了
                while (temp.next != null) {
                    temp = temp.next;
                }
                // 此时temp已经指向尾部的结点了，让temp指向下一个新结点：把当前结点创建出来，成为新的尾部结点
                temp.next = new Node(data, null);
                //每次创建结点，size++记录链表的总长度
                size++;
            }
        }
        return head;
    }

    // 1 2 3 4 5 6    假设left = 2   right = 5，left结点到right结点的数据就是需要进行反转的
    //把需要反转的节点，存入到集合中。然后再把集合倒序遍历，依次赋值给链表left结点，一直赋值到right结点。完成链表自定义位置的反转
    public Node<E> reverse(Node<E> head, int left, int right){
        //对接收的形参做完整的判断
        if(head == null || left < 1 || left > size || right < 1 || right > size
             || left == right || left > right) {
            return head;
        }

        // 1、找出左节点的起始地址。
        // 2、从左边遍历到右节点，然后把数据先存入集合。
        Node<E> first = head;       //保存头指针，最后还是需要返回头指针
        Node<E> mark = null;        //用来记录左节点位置
        //该集合存储需要反转的结点的数据，从left到right的数据
        List<E> data = new ArrayList<>();
        int index = 0;      //计数

        while (head != null) {
//头指针head刚开始进来不为空，说明现在就是第一个的头结点，已经遍历到了一个结点，index记录遍历的个数,index为1，意思就是遍历了一个结点
            //这个是自定义的链表，不是默认数组这种索引从0开始，我们是从1开始
            index++;
            if(index == left) {         //index=left说明，已经找到了左节点起始地址
//head不断指向下一个节点 左节点位置找到了。此时head头指针指向的就是左节点地址，交给mark标记。后续把需要反转的结点数据全部找到后，对mark指向的位置到最后找到的右结点位置，对这一段数据遍历
                mark = head;
            }

            //这一段数据就是需要进行反转的数据，每一次死循环都存一个需要反转的数据到集合中
            if(index >= left && index <= right) {
                //每一轮while循环，都可以遍历一个结点的数据到集合中
                data.add(head.data);
            }

            //while死循环中，index遍历到了右结点之后，就结束死循环
            if(index == right){
                break;
            }

            //继续指向下一个结点，进行下一轮while循环
            head = head.next;
        }

        // 2、倒序遍历需要反转的结点数据的集合，然后依次赋值给链表的left到right位置。这样就实现了把left到right结点的数据进行反转
        // list集合索引是从0开始的
        for (int i = data.size() - 1; i >= 0; i--) {
            E e = data.get(i);
            mark.data = e;      //mark记录的就是左节点位置
            mark = mark.next;
        }

        return first;
    }

    public void forEach(Node<E> head){
        if(head == null){
            System.out.println(head);
            return;
        }

        //如果后面head==null，那说明已经遍历结束指向了最后一个结点
        //神来之笔的遍历，判断链表的条件，还是从头结点不为空开始判断，这样更方便
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
}
